package com.example.algorithm.AList;

/**
 * @author: dangwen
 * @createDate: 2021/5/22
 * 24. 两两交换链表中的节点
 *
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 */
public class SwapPairs {

    public ListNode swapPairs1(ListNode head){
        ListNode empty = new ListNode(0);
        empty.next = head;
        ListNode temp = empty;
        while (temp.next != null && temp.next.next != null){
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            node1.next = node2.next;
            node2.next = node1;
            temp.next = node2;
            temp = node1;
        }
        return empty.next;
    }
//    public ListNode swapPairs(ListNode head) {
//        ListNode dummyHead = new ListNode(0);
//        dummyHead.next = head;
//        ListNode temp = dummyHead;
//        while (temp.next != null && temp.next.next != null) {
//            ListNode node1 = temp.next;
//            ListNode node2 = temp.next.next;
//            temp.next = node2;
//            node1.next = node2.next;
//            node2.next = node1;
//            temp = node1;
//        }
//        return dummyHead.next;
//    }


    public ListNode swapPairs(ListNode head){
        if(head == null || head.next == null){
            return head;
        }

        ListNode next = head.next;
        ListNode listNode = swapPairs(next.next);
        head.next = listNode;
        next.next = head;
        return next;
    }

}
